package Array.BinarySearch;
/**
 * 描述
 * 有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转，
 * 使数组变为[nums[k],nums[k+1],.....,nums[nums.length-1],nums[0],nums[1],.......,nums[k-1]]。
 * 给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其下标（从0开始计数），
 * 如果不存在请返回-1。
 *
 * */
class NC48 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param nums int整型一维数组
     * @param target int整型
     * @return int整型
     */
    public int search (int[] nums, int target) {
        if (nums == null || nums.length < 1) {
            return -1;
        }
        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }
        //二分查找，再怎么旋转，数组也会部分有序
        int start = 0, end = nums.length - 1;
        while(start<=end){
            int mid = (end-start)/2 + start;
            if(nums[mid] == target){
                return mid;
            }
            if(nums[0]<= nums[mid]){
                //左半部分有序,且目标值在左半部分中
                if(target >= nums[0] && nums[mid] > target){
                    end = mid-1;
                }else{
                    start = mid+1;
                }
            }else{
                //右半部分有序,且目标值在右半部分中
                if(target <= nums[end] && nums[mid] < target){
                    start = mid+1;
                }else{
                    end = mid - 1;
                }
            }
        }
        return -1;
    }
    public int search1 (int[] nums, int target) {
        // write code here
        //顺序查找 O(n)
        int i = 0;
        int j = nums.length-1;

        for(i=0;i<=j;i++){
            if(nums[i]==target){
                return i;
            }
        }
        return -1;

    }
}
